public class code02 {
//    力扣 150 从中序遍历和后续遍历序列构造二叉树
    // 这道题目的解法和上一道题目的解法是相似的，这里给了中序遍历和后序遍历

    // 首先可以先创建一个 Map 将中序遍历的下标和元素的映射关系建立起来，方便快速获取
    HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            // 这里要做到 通过 元素 获取到 下标的操作
            map.put(inorder[i], i);
        }

        int p_len = postorder.length - 1;

        TreeNode re = Build(inorder, 0, inorder.length - 1, postorder, 0, p_len);

        return re;
    }

    // 这里单独设置一个方法实现树的构建
    // 这里需要传入的参有：
    // 中序遍历的结果集
    // 后序遍历的结果集
    // 中序遍历的起始点和数组最终点
    // 后序遍历的最终点
    public TreeNode Build(int[] inorder, int i_left, int i_right, int[] postorder, int p_left, int p_right) {

        if (i_left > i_right) {
            return null;
        }

        // 在这两组数据中，根节点是后序遍历结果集中的最后一个元素
        int root_val = postorder[p_right];

        // 构造树的根节点
        TreeNode root = new TreeNode(root_val);

        // 在通过得到的后序遍历中的根节点
        // 在中序遍历的结果集中分割出左右子树
        int size = map.get(root_val) - i_left;

        // 构造右子树
        // 中序遍历的数字集合中，从 size 开始右半部分
        // 后序遍历的数字集合中，从 size 长度开始到 右半部分 - 1
        root.right = Build(inorder, i_left + size + 1, i_right, postorder, p_left + size, p_right - 1);

        // 构造左子树
        // 中序遍历的数字集合中，从 size 开始左半部分
        // 后序遍历的数字集合中，从 p_left 开始到 size - 1
        root.left = Build(inorder, i_left,i_left + size - 1, postorder, p_left, p_left + size - 1);

        return root;
    }
}
